package cn.edu.cdu.argorithm.impl;

import cn.edu.cdu.argorithm.ISlidingWindowMaximum;

import java.util.Deque;
import java.util.LinkedList;
import java.util.PriorityQueue;

public class SlidingWindowMaximum {
    public static class Solution1 implements ISlidingWindowMaximum {
        @Override
        public int[] maxSlidingWindow(int[] nums, int k) {
            int n = nums.length;
            // 初始化大根堆，大根堆排序规则为最大值排在堆顶，如果值相同则索引大的排在堆顶
            PriorityQueue<int[]> pg = new PriorityQueue<>((o1, o2) -> o1[0] != o2[0] ? o2[0] - o1[0] : o2[1] - o2[0]);
            for (int i = 0; i < k; i++) {
                // 先将k个元素放在堆顶
                pg.offer(new int[]{nums[i], i});
            }
            int ans[] = new int[n - k + 1];
            ans[0] = pg.peek()[0];
            for (int i = k; i < n; i++) {
                pg.offer(new int[]{nums[i], i});
                // 左边界下标为 i - k + 1
                while (pg.peek()[1] < i - k + 1) {
                    // 如果堆顶元素的下标在左边界左侧则出栈,直到找到在滑动窗口内的元素
                    pg.poll();
                }
                ans[i - k + 1] = pg.peek()[0];
            }
            return ans;
        }
    }

    public static class Solution2 implements ISlidingWindowMaximum{
        @Override
        public int[] maxSlidingWindow(int[] nums, int k) {
            int n = nums.length;
            Deque<Integer> q = new LinkedList<>();
            for (int i = 0; i < k; i++) {
                while(!q.isEmpty() && nums[q.peekLast()] <= nums[i]) {
                    q.pollLast();
                }
                q.addLast(i);
            }
            int[] ans = new int[n - k + 1];
            ans[0] = nums[q.peekFirst()];
            for (int i = k; i < n; i++) {
                while (!q.isEmpty() && nums[q.peekLast()] <= nums[i]) {
                    q.pollLast();
                }
                q.addLast(i);
                while(!q.isEmpty() && q.peekLast() < i - k + 1) {
                    q.pollFirst();
                }
                ans[i - k + 1] = nums[q.peekFirst()];
            }
            return ans;
        }
    }

    public static void main(String[] args) {
        Solution2 solution2 = new Solution2();
        int[] ans = solution2.maxSlidingWindow(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3);
        for (int a : ans) {
            System.out.println(a);
        }
    }
}
